package com.example.myletcodelearing.one.tree

import java.util.*


/**
 * https://offer.hi-dhl.com/#/algorithm/03-number
 * @author tgw
 * @date 2022/11/7
输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

例如，给出

前序遍历 preorder = [3,9,20,15,6,2,7]
中序遍历 inorder = [9,3,6,15,2,20,7]
复制Error复制成功
返回如下的二叉树：

3
/ \
9  20
/ \
15  7
/ \
6   2


前序遍历和中序遍历过程如下：

前序遍历：根结点 ---> 左节点 ---> 右节点
中序遍历：左节点---> 根结点 ---> 右节点
根据前序遍历的规则，可知 preorder[0] 一定是整棵二叉树的根节点，如果根节点所在的下标为 index，根据中序遍历的规则，可知中序序列 inorder：

区间 inorder[0, index - 1] 属于根节点 preorder[0] 左子树
区间 inorder[index + 1, n - 1] 属于根节点 preorder[0] 右子树
根据前序遍历的规则一定是先遍历完左子树，然后才会遍历右子树，所以前序序列 preorder：

区间 preorder[1, index] 属于根节点的 preorder[0] 左子树
区间 preorder[index+1, n -1] 属于根节点的 preorder[0] 右子树
所以算法思路如下：

根节点是Preorder数组中的第一个元素，即 preorder[0]
在Inorder数组中查找根的位置 index
在Inorder数组中，根元素左边的元素是左子树，即区间 inorder[0, index - 1]
在Inorder数组中，根元素右边的元素是右子树，即区间 inorder[index + 1, n - 1]
在preorder数组中，根元素左边的元素是左子树，即区间 preorder[1, index]
在preorder数组中，根元素右边的元素是右子树，即 preorder[index+1, n - 1]
在由左子树中的元素组成的子数组上递归调用
在由右子树中的元素组成的子数组上递归地调用
 */
private class TreeNode(val key: Int) {
    var left: TreeNode? = null
    var right: TreeNode? = null
}

fun main(args: Array<String>) {
    var pre = arrayOf(3, 9, 20, 15, 6, 2, 7)
    var inorder = arrayOf(9, 3, 6, 15, 2, 20, 7)
    val solution = Solution13.Solution()
//    var tree = solution.buildTree(pre,inorder)
    var tree = solution.buildTree2(pre, inorder)

    println("前序")
    solution.preOrderMap(tree)
    println("中序")
    solution.inOrderMap(tree)


    println("镜像树---------")
    val solution14 = Solution14.Solution()
//    solution14.mirrorTree(tree)
    solution14.mirrorTree2(tree)
    println("前序：")
    solution.preOrderMap(tree)


    println("对称树---------")

    val isSymmetry = solution14.isSymmetric4(tree)
    println("是否对称：$isSymmetry")
}

private class Solution13 {
    class Solution {
        fun buildTree(preorder: Array<Int>, inorder: Array<Int>): TreeNode? {

            return tailrecOrder(preorder, inorder)
        }

        fun buildTree2(preorder: Array<Int>, inorder: Array<Int>): TreeNode? {

            return tailrecOrder2(preorder, inorder)
        }

        tailrec fun tailrecOrder(preorder: Array<Int>, inorder: Array<Int>): TreeNode? {
            if (preorder.size <= 0 || inorder.size <= 0) {
                return null;
            }
            val key = preorder[0]
            val root = TreeNode(key)
            if (preorder.size == 1) {
                return root
            }

            val index = getRootIndex(inorder, key)
            if (index > 0 && index < preorder.size) {
                // 计算左子树，所以根节点除外，从下标1开始
                // 数组拷贝是左闭右开的区间
                var pre = Arrays.copyOfRange(preorder, 1, index + 1)
                var inor = Arrays.copyOfRange(inorder, 0, index)
                root.left = tailrecOrder(pre, inor)

                pre = Arrays.copyOfRange(preorder, index + 1, preorder.size)
                inor = Arrays.copyOfRange(inorder, index + 1, inorder.size)
                root.right = tailrecOrder(pre, inor)
            }

            return root
        }

        fun getRootIndex(inorder: Array<Int>, key: Int): Int {
            inorder.forEachIndexed { index, item ->
                if (item == key) {
                    return index
                }
            }
            return -1
        }


        fun preOrderMap(node: TreeNode?) {
            var tree = node
            if (tree != null) {
                println("值：${tree.key}")
                preOrderMap(tree.left)
                preOrderMap(tree.right)
            }
        }

        fun inOrderMap(node: TreeNode?) {
            var tree = node
            if (tree != null) {
                inOrderMap(tree.left)
                println("值：${tree.key}")
                inOrderMap(tree.right)
            }
        }


        /**
         * 前序遍历 preorder = [3,9,20,15,6,2,7]
        中序遍历 inorder = [9,3,6,15,2,20,7]
         */
        fun tailrecOrder2(preorder: Array<Int>, inorder: Array<Int>): TreeNode? {
            if (preorder.size <= 0 || inorder.size <= 0) {
                return null;
            }
            var key = preorder[0]
            var tree = TreeNode(key)

            if (preorder.size == 1) {
                return tree
            }

            var rightIndex = getRootIndex2(inorder, key)

            if (rightIndex > 0 && rightIndex < preorder.size) {
                //copyOfRange方法 数组拷贝是左闭右开的区间

                //拿到前序的 左节点相关的数据
                var pl = Arrays.copyOfRange(preorder, 1, rightIndex + 1)
                //拿到中序的 右节点相关的数据
                var pr = Arrays.copyOfRange(inorder, 0, rightIndex)
                //构建出左边全新的树
                tree.left = tailrecOrder(pl, pr)

                pl = Arrays.copyOfRange(preorder, rightIndex + 1, preorder.size)
                pr = Arrays.copyOfRange(inorder, rightIndex + 1, inorder.size)
                //构建出右边全新的树
                tree.right = tailrecOrder(pl, pr)

            }

            return tree
        }

        fun getRootIndex2(inorder: Array<Int>, key: Int): Int {
            for (i in inorder.indices) {
                if (inorder[i] == key) {
                    return i
                }
            }
            return -1
        }
    }


}


private class Solution14 {
    class Solution {
        /**
         * 根据后续遍历的特点 左 -> 右 -> 根，交换左右节点的顺序即可
         */
        fun mirrorTree(root: TreeNode?): TreeNode? {
            if (root != null) {
                mirrorTree(root.left)
                mirrorTree(root.right)
                var right = root.right
                root.right = root.left
                root.left = right

            }
            return root
        }

        fun mirrorTree2(root: TreeNode?): TreeNode? {
            if (root == null) return root

            mirrorTree2(root.left)
            mirrorTree2(root.right)
            val tmp = root.left
            root.left = root.right
            root.right = tmp
            return root
        }

        /**
         * 利用 后续遍历 非递归的方式，交换左右节点顺序
         */
        fun mirrorTree3(root: TreeNode?): TreeNode? {
            if (root == null) return root

            val stack = Stack<TreeNode>()
            stack.push(root)
            while (!stack.isEmpty()) {
                val node = stack.pop()
                if (node.left != null) stack.push(node.left)
                if (node.right != null) stack.push(node.right)

                val tmp = node.left
                node.left = node.right
                node.right = tmp
            }
            return root
        }


        /**
         * 是否为对称树
         */
        fun isSymmetric4(root: TreeNode?): Boolean {
            if (root == null) return true
            if (root.left?.key == root.right?.key) {
                return symmetric4(root.left, root.right)
            }
            return false
        }

        //[1,2,2,null,3,null,3],

        //[9,-42,-42,null,76,76,null,null,13,null,13]
        // 利用特点：
        // 左节点的左子节点的值=右节点的右子节点的值
        // 左节点的右子节点的值=右节点的左子节点的值
        fun symmetric4(left: TreeNode?, right: TreeNode?): Boolean {
            if (left == null && right == null) return true
            return if (left?.left?.key == right?.right?.key && left?.right?.key == right?.left?.key) {
                symmetric4(left?.left, right?.right) && symmetric4(right?.left, left?.right)
            } else {
                false
            }
        }

    }



}